One of the many benefits of computers is the ability quickly to evaluate complex or lengthy mathematical expressions. What may be very time consuming or impractical for a person to compute may be rather simple for a computer to calculate. As a result, a number of computer algebra systems have been developed to allow scientists, engineers, mathematicians, students, and others to use computers to more easily calculate and solve even complex mathematical equations.
As increasingly powerful as computers have become, however, computers have their limits in terms of the magnitude of the expressions they are able to accommodate. For a personal computer, a number on the order of magnitude of 109, or a number raised to the power of one billion, is too large for a typical personal computer to accommodate. A number on the order of magnitude of 1015, or a number raised to the power of a million billion, is too large for even a supercomputer to accommodate.
In addition, the capacity of a computer may limit the precision with which mathematical expressions are calculated. In most computer programs and computing environments, the precision of any calculation is limited by the word size of the computer, because the word size of the computer determines largest number that can be stored in one of the processor's registers. Arbitrary-precision arithmetic consists of a set of algorithms, functions, and data structures designed specifically to deal with numbers that can be of arbitrary size. Arbitrary-precision arithmetic is a common feature in computer algebra systems and some specific math and engineering software packages, but is rarely included in other software
Unfortunately, sometimes mathematical expressions that are too large for the computer to accommodate, or that may be calculated only to an arbitrary level of precision, may represent only intermediate values that are part of a calculation. The calculation ultimately may result in a manageable number, but if an intermediate calculation is too large for the computing system to accommodate, the calculation cannot be performed.
FIGS. 1A, 1B, and 2 further illustrate the concern by illustrating how a computing system calculates a mathematical expression. In FIG. 1A, mathematical expression 100 represents how a computing system evaluates the expression 30*2+5. Rules of precedence of operations dictate the form of mathematic expression 100, such that the product of 30*2 is calculated, then the sum of that product is added to 5. More particularly, as regarded in a tree structure, from top down, the addition operator 102, representing the last operation, is at the top of tree structure 100, over children including multiplication operator 104 and the value 5 106. In turn, multiplication operator has two children, value 30 108 and value 2 110. Values 30 108 and 2 110 also can be thought of as the “grandchildren” of addition operator 102, because values 30 108 and 2 110 are two steps removed from addition operator 102, in contrast to multiplication operator 104 and value 5 106 which are once removed from addition operator 102.
The value of mathematical expression 100 is calculated from the bottom up to give effect to the rules of precedence of operations. Thus, value 30 108 and value 2 110 are received and, moving up tree structure 100, are multiplied together upon reaching multiplication operator 104. Moving further up tree structure 100, the product determined from the multiplication of values 30 108 and 2 110 is received along with value 5 106. Moving up the hierarchical structure of mathematical expression 100, upon reaching addition operator 102, the product of values 30 108 and 2 110 are added to value 5 106.
Shown another way, once value 30 108 and value 2 110 are multiplied together, tree structure 100 of FIG. 1A becomes mathematical expression 120 of FIG. 1B. As the expression is calculated from the bottom up, mathematical expression 100 becomes simplified to mathematical expression 120. Thus, from the perspective of addition operator 102, only the children of addition operator 102, product 122 and value 5 106 are relevant; the children of each operator only are ever relevant, regardless of what the grandchildren of the term might be. Again, the hierarchical tree structure is created based on rules of precedence of operations, and the tree is calculated from the bottom up.
Unfortunately, sometimes the conventional approach cannot calculate an expression that, although manageable on the whole, includes one or more steps that the computing system is unable to calculate. For example, FIG. 2 illustrates a mathematical expression 200 representing how a computing system would calculate the expression 12345100000000000000% 18970907, where “%” represents the modulus division operator. In tree structure 200, the modulus division operator 202 has children that include the exponential operator 204, which in turn has children base 12345 208 and exponent 1000000000000000 210, and quotient 18970907 204. The result of modulus division yields a result which, at most, is one less than the quotient or, in the example of FIG. 2, is quotient 18970906 206. This is a value that is manageable within even a simple computing system. By contrast, however, calculating the expression 123451000000000000000 would overwhelm even most supercomputers. Accordingly, even though the overall result of the expression represented by mathematical expression 200 is manageable, processing of mathematical expression 200 ends at the calculation of 12345100000000000000.
It would therefore be desirable to provide a method and system for a computing system to automatically calculate the result of mathematical expressions when the overall result of the mathematical expression is manageable by the computing system, even when the mathematical expression includes a calculation the computing system is not able to accommodate.